0108. 将有序数组转换为二叉搜索树【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归（取中点建树）

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

---

示例 1：

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

---

示例 2：

输入：nums = [1,3]

输出：[3,1]

解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

---

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按 严格递增 顺序排列

2. 🎯 s.1 - 递归（取中点建树）

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* build(int* nums, int left, int right) {
    if (left > right) return NULL;
    int mid = left + (right - left) / 2;
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = nums[mid];
    node->left = build(nums, left, mid - 1);
    node->right = build(nums, mid + 1, right);
    return node;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return build(nums, 0, numsSize - 1);
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  // 边界条件：数组为空
  if (nums.length === 0) {
    return null
  }

  // 找到中间元素作为根节点
  const mid = Math.floor(nums.length / 2)
  const root = new TreeNode(nums[mid])

  // 递归构造左右子树
  root.left = sortedArrayToBST(nums.slice(0, mid))
  root.right = sortedArrayToBST(nums.slice(mid + 1))

  return root
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])
        return root

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度，每个元素恰好构建一个节点
• 空间复杂度：$O(\log n)$，递归栈深度为树的高度，平衡二叉树高度为 $O(\log n)$

算法思路：

• 有序数组天然满足 BST 的中序遍历序列，取中间元素作为根节点可确保树高度平衡
• 递归地将左半部分构建为左子树、右半部分构建为右子树
• 每层递归区间缩小一半，最终构造出高度平衡的 BST